/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 强仔
 * Date: 2021-11-17
 * Time: 19:21
 */
public class TestDemo {
    /*
    * 贪心算法，局部最优解
    * 防止平衡字符串嵌套
    * */
    public int balancedStringSplit(String s) {
        char[] chars = s.toCharArray();
        int cnt = 0;
        int balance = 0;
        for (int i = 0; i < s.length(); i++) {
            if(chars[i] == 'R'){
                balance--;
            }
            if(chars[i] == 'L'){
                balance++;
            }
            if(balance == 0){
                cnt++;
            }
        }

        return cnt;
    }

    /*
    * 买卖股票最佳时机
    * 看趋势，低买高卖
    *       连续上升：最低点买进，最高点卖出   ----> 每天买卖的 绝对利润相同
    *       连续下跌，不买卖
    *
    * */
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i-1]){
                profit += prices[i-1] - prices[i];
            }
        }
        return profit;
    }

    /*
    * 跳跃游戏
    * 贪心：站在每一个位置，更新可以到达的最大位置
    *
    * maxIndex是nums[0],maxIndex以前的位置都可以到达，站在不同的位置上，更新这个maxIndex，如果maxIndex包括最后一个位置，true
    * */
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int maxIndex = 0;
        for (int i = 0; i <= len-1; i++) {
            if(i <= maxIndex){
                maxIndex = nums[i] + i > maxIndex ? nums[i] + i: maxIndex;
                if(maxIndex >= len-1){
                    return true;
                }
                //此位置是0
            }else{
                return false;
            }
        }
        return true;
    }

}
